The web offers a variety of services that can be accessed by an individual using a web browser. Web Services may be information services (e.g., routing services that provide driving directions, yellow-page services that provide information about places of interest, movie-time services for movie listings, etc.) or action facilitating services (e.g., Web Services enabling specific actions such as buying books, booking flights and hotels, operating webcams, etc.). In addition, Web Services may provide networked access to electronic devices (e.g., online weather services providing the wind speed and temperature to a weather station) or be provided by electronic devices (e.g., a GPS device providing the service of specifying its location, a mobile phone providing a communication service, a PDA providing an interface service, etc.).
Web Service composition is the task of composing sets of Web Services to achieve more complex goals. For example, planning a vacation may require coordinating flights, hotels, rental cars, places of interest to visit, etc. A user can plan a vacation by visiting various travel web sites and coordinating the choices manually, but that is a complex and tedious task. In addition, such a manual solution may not allow a user to find an optimal match because of a large number of possible combinations of choices. In another example, tourists may need on-going information about the attractions of interest in their vicinity as they are traveling. Such information cannot be provided by a single device. Instead, it involves multiple services from multiple devices, including, for example, the GPS, a communication service by a user cellular phone, an interface service by a user PDA, and a yellow-pages service. Furthermore, none of these devices are themselves essential because the services they provide may be available through some other devices. For example, a camcorder can be substituted for the PDA to display information to the tourist, an Internet connection on a PDA can be substituted for the cellular phone, etc. This gives great flexibility in mixing and matching devices that can be configured to provide complex services, as they are needed.